﻿// 0813train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

/*
 为将员工取餐排队时间降低为0，食堂的供餐速度必须要足够快。
 现在需要根据以往员工取餐的统计信息，计算出一个刚好能达成排队时间为0的最低供餐速度。
 即，食堂在每个单位时间内必须至少做出多少份盒饭才能满足要求。

输入
- 第1行为一个正整数N，表示食堂开餐时长。1 <= N <= 1000
- 第2行为一个正整数M，表示开餐前食堂已经准备好的盒饭份数。Pi <= M <= 1000
- 第3行为N个正整数，用空格分隔，依次表示开餐时间内按时间顺序每个单位时间进入食堂取餐的人数Pi
- 1 <= i <= N，0 <= Pi <= 100
输出
一个整数，能满足题目要求的最低供餐速度(每个单位时间需要做出多少份盒饭)。

每人只取一份盒饭。需要满足排队时间为0，必须保证取餐员工到达食堂时，食堂库存盒饭数量不少于本次来取餐的人数。
第一个单位时间来取餐的员工只能取开餐前食堂准备好的盒饭。
每个单位时间里制作的盒饭只能供应给后续单位时间来的取餐的员工，食堂在每个单位时间里制作的盒饭数量是相同的。

示例
输入
3
14
10 4 5
输出
3

本样例中，总共有3批员工就餐，每批人数分别为10、4、5。
开餐前食堂库存14份。3份餐饭，具体情况如下：
第一个单位时间来的10位员工直接从库存取餐，取餐后库存剩余4份盒饭，加上第一个单位时间做出的3份，库存有7份。
第二个单位时间来的4员工从库存的7份中取4份，取餐后库存剩余3份盒饭，加上第二个单位时间做出的3份，库存有6份。
第三个单位时间来的员工从库存的6份中取5份，库存足够。

2份餐饭，则情况如下：
第一个单位时间来的10位员工直接从库存取餐，取餐后库存剩余4份盒饭，加上第一个单位时间做出的2份，库存有6份。
第二个单位时间来的4员工从库存的6份中取4份，取餐后库存剩余2份盒饭，加上第二个单位时间做出的2份，库存有4份。
第三个单位时间来的员工需要取5份，但库存只有4份，库存不够。

 */

bool IfEnough(vector<int>& oh_vec, int curr_count, int new_count)
{
	int result = true;
	int curr_remain = curr_count;
	for (auto&num:oh_vec)
	{
		if (curr_remain<num)
		{
			result = false;
			break;
		}
		curr_remain += new_count;
		curr_remain -= num;
	}

	return result;
	//IfEnough
}


void solve01(vector<int>&origin_vec, int curr_count)
{
	//result的范围0-max(vector<int>)
	//IfEnough 如果足够,当前>目标，减少数量，right=mid+1
	//不够，当前<目标，增加数量, left=mid
	int vec_size = origin_vec.size();
	long long sum = 0;
	for (int i=0; i< vec_size; i++)
	{
		sum += origin_vec[i];
	}
	if (curr_count>=sum)
	{
		cout << 0;
		return;
	}

	vector<int>oh_vec = origin_vec;
	sort(oh_vec.begin(), oh_vec.end());
	int left = 1;
	int right = oh_vec[vec_size - 1];

	int result = INT_MAX;
	while (left<right)
	{
		int mid = left + (right - left) / 2;
		//cout << mid << endl;
		if (IfEnough(origin_vec, curr_count, mid))
		{
			//过剩，减少产出速度
			result = min(result, mid);
			right = mid;
		}
		else
		{
			left = mid+1;
		}
	}
	
	cout << result;
	//solve01------
}


/*
 孙悟空喜欢吃蟠桃，一天他趁守卫蟠桃园的天兵天将离开了而偷偷的来到王母娘娘的蟠桃园偷吃蟠桃。
已知蟠桃园有 N 棵蟠桃树，第 i棵蟠桃树上有 N[i]（大于 0）个蟠桃，天兵天将将在 H（不小于蟠桃树棵数）小时后回来。
孙悟空可以决定他吃蟠桃的速度 K （单位：个/小时），
每个小时他会选择一颗蟠桃树，从中吃掉 K 个蟠桃，如果这棵树上的蟠桃数小于 K ，
他将吃掉这棵树上所有蟠桃，然后这一小时内不再吃其余蟠桃树上的蟠桃。
孙悟空喜欢慢慢吃，但仍想在天兵天将回来前将所有蟠桃吃完。
求孙悟空可以在 H 小时内吃掉所有蟠桃的最小速度 K（K 为整数）。

输入描述
第一行输入为 N 个数字，N 表示桃树的数量，这 N 个数字表示每颗桃树上蟠桃的数量
第二行输入为一个数字，表示守卫离开的时间 H。
其中数字通过空格分割，N、H 为正整数，每颗树上都有蟠桃，且 0 < N < 10000，0 < H < 10000。
输出描述
吃掉所有蟠桃的最小速度 K（K 为整数），无解或者输入异常时输出 0 。

示例1
输入
3 11 6 7 8
1
输出
0

示例2
输入
3 11 6 7 8
5
输出
11
 */

int CalculateTime(vector<int>& oh_vec, int speed)
{
	if (speed == 0) return INT_MAX;

	int total_time = 0;
	for (auto&amount:oh_vec)
	{
		int curr_time = ceil(static_cast<double>(amount) / speed);
		total_time += curr_time;
	}
	return total_time;
	//CalculateTime
}

void solve02(vector<int>&origin_vec, int limit)
{
	//time<=limit成立
	int vec_size = origin_vec.size();
	vector<int>sort_vec = origin_vec;
	sort(sort_vec.begin(), sort_vec.end());
	int left = 0;
	int right = sort_vec[vec_size - 1] + 1;

	int result = INT_MAX;
	while (left<right)
	{
		int mid = left + (right - left) / 2;
		//cout << mid << endl;
		if (CalculateTime(origin_vec, mid)<=limit)
		{
			//符合要求，缩小速度
			result = min(result, mid);
			right = mid;
		}
		else
		{
			left = mid + 1;
		}
	}

	if (result==INT_MAX)
	{
		cout << 0;
		return;
	}

	cout << result;

	//solve02------
}

/*
 部门在进行需求开发时需要进行人力安排。
 当前部门需要完成 N 个需求，需求用 requirements[i] 表示，
 requirements[i] 表示第 i 个需求的工作量大小，单位：人月。
 这部分需求需要在 M 个月内完成开发，进行人力安排后每个月的人力是固定的。

目前要求每个月最多有 2 个需求开发，并且每个月需要完成的需求不能超过部门人力。
请帮部门评估在满足需求开发进度的情况下，每个月需要的最小人力是多少？

输入描述
输入第一行为 M ，第二行为 requirements 。
M 表示需要开发时间要求，requirements 表示每个需求工作量大小
N 为 requirements 长度，1 ≤ N / 2 ≤ M ≤ N ≤ 10000，1 ≤ requirements[i]≤ 10^9
输出描述
对于每一组测试数据，输出部门需要人力需求，行末无多余的空格。

输入
3
3 5 3 4
输出
6

输入数据两行，第一行输入数据 3 表示开发时间要求，第二行输入数据表示需求工作量大小，输出数据一行，表示部门人力需求。
当选择人力为6时，2个需求量为3的工作可以在1个月里完成，其他2个工作各需要1个月完成。可以在3个月内完成所有需求。
当选择人力为5时，4个工作各需要1个月完成，一共需要4个月才能完成所有需求。
因此6是部门最小的人力需求。

输入
3
3 5 3 4
输出
6
3个月内需要完成3 5 3 4，一次可以做2个 int right = ?我觉得是最大两个数加起来
 */

int CaculteNeedTime03(vector<int>&sort_vec, int limit)
{
	int vec_size = sort_vec.size();
	vector<int>cache_vec;
	for (int i=0; i< vec_size; i++)
	{
		int curr_num = sort_vec[i];
		if (curr_num<limit && i+1< vec_size)
		{
			int next_num = sort_vec[i + 1];
			if (curr_num+next_num<=limit)
			{
				cache_vec.push_back(curr_num + next_num);
				i++;
				continue;
			}
			
		}
		cache_vec.push_back(curr_num);
	}
	return cache_vec.size();
	//CaculteNeedTime03
}

void solve03(vector<int>&oh_vec, int time_limit)
{
	int vec_size = oh_vec.size();
	int left = 0;
	sort(oh_vec.begin(), oh_vec.end());
	int right = oh_vec[vec_size - 1] + oh_vec[vec_size - 2] + 1;

	int result = INT_MAX;
	while (left<right)
	{
		int mid = left + (right - left) / 2;
		cout << mid << endl;
		if (CaculteNeedTime03(oh_vec,mid)<=time_limit)
		{
			result = min(result, mid);
			//人力足够，可以往低调
			right = mid;
		}
		else
		{
			//人力不足往高调
			left = mid + 1;
		}
	}
	cout << result;
	//solve03------
}

int main()
{
	{
		//3
		//3 5 3 4
		vector<int>oh_vec = { 70626,93161,1432,4933,16953,95829,87720,34332,66147,7938,49041,78529,36832,99644,35034,4795,85812,46044,81381,50286,67349,46232,54153,47208,90268,88256,39184,93420,74561,44674,48855,3489,80295,85553,69222,90127,45964,4311,31159,10405,22991,90584,29238,8263,95117,37689,50091,42164,4269,75246,82346,70529,15688,92120,16721,60408,65229,73126,81476,59782,91007,81284,25235,27644,6620,2502,23190,96525,35430,46354,61465,89558,77287,81447,40082,34040,37035,63473,96863,45776,78360,85019,12769,11778,95922,41133,45681,6469,47154,32975,81291,33417,9877,8581,58316,21904,95667,319,78516,58812,5582,55526,71938,80876,94045,59982,77602,22995,4631,1991,12308,95388,50197,49723,90663,51657,6090,75886,56889,27511,29127,13728,65678,68125,24690,86100,7902,35768,59069,85443,9832,7170,12530,72103,85581,46393,79533,33755,13878,51713,74246,66221,73578,4763,26096,96218,13583,98333,94393,36727,66945,75044,47339,82006,49662,2807,543,83154,62296,78973,57774,1324,86623,95524,98944,33585,68081,5152,35328,4815,31314,57444,89539,87826,1661,64966,58461,67463,33628,63562,9120,47816,55842,35855,95497,55380,81847,59147,42632,97886,99376,30896,81376,85679,57082,57182,48467,52062,91075,94393,49888,28935,730,50667,37443,65917,53048,16218,91169,93169,21728,55357,28676,53567,19897,53420,96307,9267,10241,55711,49219,20383,78384,93214,54751,48541,79647,70189,1108,53305,84202,57790,80706,96655,70443,14092,76547,89586,25009,67740,46392,47991,25364,59507,77301,17902,28053,36589,3647,81292,82928,18195,59695,92009,29409,34017,36343,90515,6245,46392,54602,66827,29545,80597,8157,95259,63804,32954,59124,44839,71283,6931,97208,61782,3867,23509,74258,83574,80774,30685,14748,76134,90992,37781,98306,19893,53496,83690,39749,5926,47601,91576,5021,76692,37221,20796,94265,47892,29287,8431,61581,15457,77198,19241,29462,13099,35245,66949,35762,64054,37815,22911,54889,31844,33160,68792,29317,20769,43644,54517,80514,8450,42228,71686,38271,79221,1567,25738,86445,7119,42026,44529,56011,35071,41771,96772,5563,86631,65554,59177,28741,44012,85856,46022,91205,23186,52401,57781,93833,6673,87200,30487,37395,13339 };
		//int limit = 32939;
		//sort(oh_vec.begin(), oh_vec.end());
		//cout << CaculteNeedTime03(oh_vec, limit);
		int time_limit = 323;
		//int time_limit;
		//cin >> time_limit;
		//cin.ignore();

		//vector<int>oh_vec;
		//string input;
		//getline(cin, input);
		//stringstream oh_sstream(input);
		//string token;
		//while (oh_sstream>>token)
		//{
		//	oh_vec.push_back(stoi(token));
		//}

		//for (auto&num:oh_vec)
		//{
		//	cout << num << ',';
		//}
		//CaculteNeedTime03
		solve03(oh_vec, time_limit);
		return 0;
	}
	{
		//3 11 6 7 8
		//5 输出11
		vector<int>oh_vec = { 3,11,6,7,8 };
		int limit = 1;
		//string input;
		//getline(cin, input);
		//stringstream oh_sstream(input);
		//string token;
		//vector<int>oh_vec;
		//while (oh_sstream>>token)
		//{
		//	oh_vec.push_back(stoi(token));
		//}

		//
		//int limit;
		//cin >> limit;
		solve02(oh_vec, limit);

		return 0;
	}

	//3
	//14
	//10 4 5
	//int target = 14;
	//vector<int>oh_vec = { 10,4,5 };
	//76 23 35 11 87 8 100 54 100 20 91 25 38 7 100 39 93 97 96 33 11 77 87 76 9 76 73 8 24 100 1 82 62 15 71 41 80 6 74 10 59 56 70 22 43 84 6 87 74 62 18 64 31 4 98 26 87 30 3 20 90 41 50 12 22 40 89 59 27 3 28
	int target = 794;
	vector<int>oh_vec = { 76,23,35,11,87,8,100,54,100,20,91,25,38,7,100,39,93,97,96,33,11,77,87,76,9,76,73,8,24,100,1,82,62,15,71,41,80,6,74,10,59,56,70,22,43,84,6,87,74,62,18,64,31,4,98,26,87,30,3,20,90,41,50,12,22,40,89,59,27,3,28 };
	//int vec_size, target;
	//cin >> vec_size >> target;
	//vector<int>oh_vec(vec_size);
	//for (int i=0; i<vec_size; i++)
	//{
	//	cin >> oh_vec[i];
	//}

	//for (auto&num:oh_vec)
	//{
	//	cout << num << ',';
	//}
	solve01(oh_vec, target);
	//int curr_count = 794;
	//int new_count = 39;
	//cout << IfEnough(oh_vec, curr_count, new_count);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
